package arithmetic.tree;

import java.util.*;

/**
 * 二叉树的遍历
 *
 * 中序遍历:先遍历左子树，反问根节点，遍历右子树
 *
 * 前序遍历:先访问父节点，然后遍历左子树，最后遍历右子树
 *
 * 后序遍历:先遍历左子树，再遍历右子树，最后反问根节点
 *
 * @author zhangzg
 * @date 2022/11/16
 */
public class TreeTest {

    public static void main(String[] args) {
        Deque<Integer> stack = new LinkedList<>();
    }

    public List<Integer> inorderTraversalWhile(TreeNode root) {
        List<Integer> list=new ArrayList<>();
        Deque<TreeNode> stack=new LinkedList<>();
        while(root != null || !stack.isEmpty()){
            while(root!=null){
                stack.push(root);
                root=root.left;
            }
            root=stack.pop();
            list.add(root.val);
            root=root.right;
        }
        return list;
    }

    /**
     * 二叉树的中序遍历
     * @param root
     * @return
     */
    public List<Integer> inorderTraversal(TreeNode root){
        List<Integer> list = new ArrayList<>();
        recursiveMidTree(root,list);
        return list;
    }

    /**
     * 中序遍历-递归树
     */
    public void recursiveMidTree(TreeNode root,List<Integer> list){
        if(root == null){
            return;
        }
        recursiveMidTree(root.left,list);
        list.add(root.val);
        recursiveMidTree(root.right,list);
    }

    /**
     * 前序遍历
     */
    public void recursiveBeforeTree(TreeNode root,List<Integer> list){
        if(root == null){
            return;
        }
        list.add(root.val);
        recursiveBeforeTree(root.left,list);
        recursiveBeforeTree(root.right,list);
    }

    /**
     * 后序遍历
     */
    public void recursiveAfterTree(TreeNode root,List<Integer> list){
        if(root == null){
            return;
        }
        recursiveAfterTree(root.left,list);
        recursiveAfterTree(root.right,list);
        list.add(root.val);
    }



    /**
     * LeetCode-110 平衡二叉树
     * 给定一个二叉树，判断它是否是高度平衡的二叉树
     * 高度平衡二叉树定义:一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1
     * 递归
     */
    public static boolean isBalanced(TreeNode root){
        if (root == null) {
            return true;
        }
        return helper(root) != -1;
    }

    private static int helper(TreeNode root) {
        if (root == null){
            return 0;
        }
        int left = helper(root.left);
        int right = helper(root.right);
        if(left == -1 || right == -1 || Math.abs(left - right) > 1){
            return -1;
        }
        return Math.max(left,right) + 1;
    }

}


class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}